use std::collections::{BinaryHeap, HashMap};
use super::solution::Solution;

impl Solution {
    pub fn network_delay_time(times: Vec<Vec<i32>>,n: i32,mut k: i32) -> i32 {
        let k=(k-1) as usize;
        let mut  matrix=Vec::new();
        for i in 0..n as usize {
            matrix.push([i32::MAX].repeat(n as usize));
            matrix[i][i]=0
        }
        for p in times {
            matrix[(p[0]-1 )as usize][(p[1]-1 )as usize] = p[2];
        }
        let mut confired =[0].repeat(n as usize);
        confired[k]=1;
        loop    {
            let mut min_dis=i32::MAX;
            let mut min_id =None;
            for i in 0..n as usize {
                if confired[i]==1{
                    continue
                }
                if min_dis>matrix[k ][i] {
                    min_dis=matrix[k][i];
                    min_id = Some(i);
                }
            }
            if min_id.is_none(){
                break;
            }
            let id= min_id.unwrap();
            confired[id]=1;
            let dd = matrix[k][id];
            for i in 0..n as usize {
                if confired[i]==1 || matrix[id][i]==i32::MAX{
                    continue
                }
                if matrix[k][i]>dd+matrix[id][i]{
                    matrix[k][i] = dd+matrix[id][i];
                }
            }
        }
        let mut ans = 0;
        for i in 0..n as usize {
            if ans<matrix[k][i] {
                ans =matrix[k][i];
            }
        }
        if ans ==i32::MAX{
            -1
        }else{
            ans
        }
    }
}
#[cfg(test)]
mod tests {
    use super::Solution;
    #[test]
    fn test_network_delay_time() {
        Solution::network_delay_time(vec![vec![2,1,1],vec![2,3,1],vec![3,4,1]],4,2);
    }
}